#!/usr/bin/env python
# -*- coding: UTF-8 -*-
'''
@Project ：V2
@File    ：T9.py
@IDE     ：PyCharm
@Author  ：郭星
@Date    ：2025/10/17 23:13
'''
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
'''
@Project ：V2
@File    ：P8.py
@IDE     ：PyCharm
@Author  ：郭星
@Date    ：2025/10/15 23:47
'''
import os
import json
import random
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import argparse
import csv
import time
from datetime import datetime
from typing import List, Tuple, Dict, Optional

# 设置中文显示
plt.rcParams["font.family"] = ["SimHei", "SimHei", "SimHei"]
plt.rcParams["axes.unicode_minus"] = False  # 解决负号显示问题


class GasSchedulingInstanceGenerator:
    """气体调度算例生成器与加载器（兼容之前生成的算例）"""

    @staticmethod
    def generate_instance(num_workpieces: int,
                          num_components: int,
                          num_inflation_eq: int,
                          num_analysis_eq_per_component: int,
                          num_clean_eq: int = 1,
                          num_shake_eq: int = 1,
                          clean_time: int = 5,
                          shake_unit_time: int = 2,
                          min_inflation_time: int = 5,
                          max_inflation_time: int = 15,
                          min_analysis_time: int = 3,
                          max_analysis_time: int = 10,
                          save_path: Optional[str] = None) -> Dict:
        """生成单个算例"""
        inflation_time = np.random.randint(min_inflation_time, max_inflation_time + 1,
                                           size=num_workpieces)
        analysis_time = np.random.randint(min_analysis_time, max_analysis_time + 1,
                                          size=(num_workpieces, num_components))

        instance = {
            'problem_type': 'gas_scheduling',
            'parameters': {
                'num_workpieces': num_workpieces,
                'num_components': num_components,
                'num_inflation_eq': num_inflation_eq,
                'num_analysis_eq_per_component': num_analysis_eq_per_component,
                'num_clean_eq': num_clean_eq,
                'num_shake_eq': num_shake_eq
            },
            'processing_times': {
                'inflation_time': inflation_time.tolist(),
                'analysis_time': analysis_time.tolist(),
                'clean_time': clean_time,
                'shake_unit_time': shake_unit_time
            },
            'metadata': {
                'min_inflation_time': min_inflation_time,
                'max_inflation_time': max_inflation_time,
                'min_analysis_time': min_analysis_time,
                'max_analysis_time': max_analysis_time
            }
        }

        if save_path:
            os.makedirs(os.path.dirname(save_path), exist_ok=True)
            with open(save_path, 'w', encoding='utf-8') as f:
                json.dump(instance, f, ensure_ascii=False, indent=2)
            print(f"算例已保存至: {save_path}")

        return instance

    @staticmethod
    def generate_multiple_instances(base_dir: str = "instances"):
        """生成多规模算例（设备数量随工件数增加而增多）"""
        instance_sizes = [
            # 小规模：5工件 → 2清洗设备 + 2摇匀设备
            {'num_workpieces': 5, 'num_components': 2,
             'num_inflation_eq': 2, 'num_analysis_eq_per_component': 1,
             'num_clean_eq': 2, 'num_shake_eq': 2,
             'clean_time': 5, 'shake_unit_time': 2},
            # 中规模：10工件 → 3清洗设备 + 3摇匀设备
            {'num_workpieces': 10, 'num_components': 4,
             'num_inflation_eq': 3, 'num_analysis_eq_per_component': 2,
             'num_clean_eq': 3, 'num_shake_eq': 3,
             'clean_time': 5, 'shake_unit_time': 2},
            # 大规模：20工件 → 4清洗设备 + 4摇匀设备
            {'num_workpieces': 20, 'num_components': 6,
             'num_inflation_eq': 5, 'num_analysis_eq_per_component': 3,
             'num_clean_eq': 4, 'num_shake_eq': 4,
             'clean_time': 5, 'shake_unit_time': 2},
            # 超大规模：50工件 → 6清洗设备 + 6摇匀设备
            {'num_workpieces': 50, 'num_components': 8,
             'num_inflation_eq': 8, 'num_analysis_eq_per_component': 4,
             'num_clean_eq': 6, 'num_shake_eq': 6,
             'clean_time': 5, 'shake_unit_time': 2}
        ]

        for i, size_params in enumerate(instance_sizes):
            size_name = f"size_{i + 1}"
            size_dir = os.path.join(base_dir, size_name)

            for j in range(3):
                instance_path = os.path.join(size_dir, f"instance_{j + 1}.json")
                GasSchedulingInstanceGenerator.generate_instance(
                    **size_params,
                    save_path=instance_path
                )

    @staticmethod
    def load_instance(file_path: str) -> Dict:
        """加载算例文件并验证格式（兼容旧算例）"""
        if not os.path.exists(file_path):
            raise FileNotFoundError(f"算例文件不存在: {file_path}")

        with open(file_path, 'r', encoding='utf-8') as f:
            instance = json.load(f)

        # 验证必要字段（兼容可能缺少清洗/摇匀参数的旧算例）
        required_keys = ['problem_type', 'parameters', 'processing_times']
        for key in required_keys:
            if key not in instance:
                raise ValueError(f"算例格式错误，缺少必要字段: {key}")

        # 为旧算例添加默认的清洗和摇匀参数（如果缺失）
        if 'num_clean_eq' not in instance['parameters']:
            instance['parameters']['num_clean_eq'] = 1
            print(f"警告：算例缺少清洗设备数量，使用默认值: 1")
        if 'num_shake_eq' not in instance['parameters']:
            instance['parameters']['num_shake_eq'] = 1
            print(f"警告：算例缺少摇匀设备数量，使用默认值: 1")
        if 'clean_time' not in instance['processing_times']:
            instance['processing_times']['clean_time'] = 5
            print(f"警告：算例缺少清洗时间，使用默认值: 5")
        if 'shake_unit_time' not in instance['processing_times']:
            instance['processing_times']['shake_unit_time'] = 2
            print(f"警告：算例缺少摇匀单位时间，使用默认值: 2")

        return instance

    @staticmethod
    def list_instances(directory: str = ".") -> List[str]:
        """列出指定目录下所有JSON算例文件"""
        instance_files = []
        for root, _, files in os.walk(directory):
            for file in files:
                if file.endswith(".json"):
                    # 简单验证是否为气体调度算例
                    try:
                        with open(os.path.join(root, file), 'r') as f:
                            data = json.load(f)
                            if data.get('problem_type') == 'gas_scheduling':
                                instance_files.append(os.path.join(root, file))
                    except:
                        continue
        return sorted(instance_files)


class BaseSchedulingAlgorithm:
    """调度算法基类（支持多清洗/摇匀设备 + 上下结构甘特图）"""

    def __init__(self,
                 instance: Dict,
                 max_iter: int = 100,
                 name: str = "算法"):
        params = instance['parameters']
        processing_times = instance['processing_times']

        # 基础参数
        self.num_workpieces = params['num_workpieces']
        self.num_components = params['num_components']
        self.num_inflation_eq = params['num_inflation_eq']
        self.num_analysis_eq_per_component = params['num_analysis_eq_per_component']
        self.inflation_time = np.array(processing_times['inflation_time'])
        self.analysis_time = np.array(processing_times['analysis_time'])

        # 多设备参数（动态获取）
        self.num_clean_eq = params['num_clean_eq']
        self.num_shake_eq = params['num_shake_eq']
        self.clean_time = processing_times['clean_time']
        self.shake_unit_time = processing_times['shake_unit_time']
        self.shake_time = np.array([self.num_components * self.shake_unit_time
                                    for _ in range(self.num_workpieces)])

        self.max_iter = max_iter
        self.name = name

        self.best_solution = None
        self.best_time = float('inf')
        self.iteration_best_times = []
        self.execution_time = 0  # 记录算法执行时间

    def initialize_solution(self) -> Dict:
        """初始化解（多设备适配）"""
        # 1. 清洗阶段：随机分配到多台设备
        clean_order = random.sample(range(self.num_workpieces), self.num_workpieces)
        clean_eq = [random.randint(0, self.num_clean_eq - 1)
                    for _ in range(self.num_workpieces)]

        # 2. 充装阶段
        inflation_order = random.sample(range(self.num_workpieces), self.num_workpieces)
        inflation_eq = [random.randint(0, self.num_inflation_eq - 1)
                        for _ in range(self.num_workpieces)]

        # 3. 摇匀阶段：随机分配到多台设备
        shake_order = random.sample(range(self.num_workpieces), self.num_workpieces)
        shake_eq = [random.randint(0, self.num_shake_eq - 1)
                    for _ in range(self.num_workpieces)]

        # 4. 分析阶段
        analysis_order = random.sample(range(self.num_workpieces), self.num_workpieces)
        component_groups = []
        group_test_order = []
        analysis_eq = []
        for _ in range(self.num_workpieces):
            max_groups = random.randint(1, self.num_components)
            groups = []
            for i in range(self.num_components):
                if i < max_groups:
                    groups.append(i)
                else:
                    groups.append(random.randint(0, max_groups - 1))
            component_groups.append(groups)
            unique_groups = list(sorted(set(groups)))
            random.shuffle(unique_groups)
            group_test_order.append(unique_groups)
            eq_for_workpiece = []
            for group_id in unique_groups:
                components_in_group = [j for j, g in enumerate(groups) if g == group_id]
                eq_for_group = [random.randint(0, self.num_analysis_eq_per_component - 1)
                                for _ in components_in_group]
                eq_for_workpiece.append(eq_for_group)
            analysis_eq.append(eq_for_workpiece)

        return {
            'clean_order': clean_order,
            'clean_eq': clean_eq,
            'inflation_order': inflation_order,
            'inflation_eq': inflation_eq,
            'shake_order': shake_order,
            'shake_eq': shake_eq,
            'analysis_order': analysis_order,
            'component_groups': component_groups,
            'group_test_order': group_test_order,
            'analysis_eq': analysis_eq
        }

    def calculate_completion_time(self, solution: Dict) -> float:
        """计算四阶段总时间（多设备适配）"""
        # 1. 清洗阶段：多设备时间计算
        clean_machine_time = [0] * self.num_clean_eq
        workpiece_clean_end = {}
        for workpiece in solution['clean_order']:
            eq = solution['clean_eq'][workpiece]
            start_time = clean_machine_time[eq]
            end_time = start_time + self.clean_time
            clean_machine_time[eq] = end_time
            workpiece_clean_end[workpiece] = end_time
        clean_completion_time = max(clean_machine_time)

        # 2. 充装阶段
        inflation_machine_time = [0] * self.num_inflation_eq
        workpiece_inflation_end = {}
        for workpiece in solution['inflation_order']:
            eq = solution['inflation_eq'][workpiece]
            start_time = max(inflation_machine_time[eq], workpiece_clean_end.get(workpiece, 0))
            end_time = start_time + self.inflation_time[workpiece]
            inflation_machine_time[eq] = end_time
            workpiece_inflation_end[workpiece] = end_time
        inflation_completion_time = max(inflation_machine_time)

        # 3. 摇匀阶段：多设备时间计算
        shake_machine_time = [0] * self.num_shake_eq
        workpiece_shake_end = {}
        for workpiece in solution['shake_order']:
            eq = solution['shake_eq'][workpiece]
            start_time = max(shake_machine_time[eq], workpiece_inflation_end.get(workpiece, 0))
            end_time = start_time + self.shake_time[workpiece]
            shake_machine_time[eq] = end_time
            workpiece_shake_end[workpiece] = end_time
        shake_completion_time = max(shake_machine_time)

        # 4. 分析阶段
        analysis_machine_time = [[0 for _ in range(self.num_analysis_eq_per_component)]
                                 for _ in range(self.num_components)]
        for workpiece in solution['analysis_order']:
            if workpiece < 0 or workpiece >= self.num_workpieces:
                continue
            start_analysis_time = workpiece_shake_end.get(workpiece, 0)
            group_test_order = solution['group_test_order'][workpiece]
            analysis_eq = solution['analysis_eq'][workpiece]

            for group_idx, group_id in enumerate(group_test_order):
                if group_idx < 0 or group_idx >= len(analysis_eq):
                    continue
                components_in_group = [j for j, g in enumerate(solution['component_groups'][workpiece])
                                       if g == group_id]
                eq_for_group = analysis_eq[group_idx]
                if len(eq_for_group) != len(components_in_group):
                    eq_for_group = [random.randint(0, self.num_analysis_eq_per_component - 1)
                                    for _ in components_in_group]
                    analysis_eq[group_idx] = eq_for_group

                group_ready_time = start_analysis_time
                for comp_idx, component in enumerate(components_in_group):
                    if comp_idx < 0 or comp_idx >= len(eq_for_group):
                        continue
                    eq = eq_for_group[comp_idx]
                    group_ready_time = max(group_ready_time, analysis_machine_time[component][eq])

                max_analysis_time = max(
                    self.analysis_time[workpiece][component]
                    for comp_idx, component in enumerate(components_in_group)
                    if comp_idx < len(eq_for_group)
                ) if components_in_group else 0
                group_end_time = group_ready_time + max_analysis_time

                for comp_idx, component in enumerate(components_in_group):
                    if comp_idx < 0 or comp_idx >= len(eq_for_group):
                        continue
                    eq = eq_for_group[comp_idx]
                    analysis_machine_time[component][eq] = group_end_time
                start_analysis_time = group_end_time

        analysis_completion_time = max(max(machine_times) for machine_times in analysis_machine_time)

        # 总时间：四阶段最大值
        total_time = max(clean_completion_time, inflation_completion_time,
                         shake_completion_time, analysis_completion_time)
        return total_time

    def get_schedule_details(self, solution: Dict) -> Tuple[Dict, Dict, Dict, Dict]:
        """返回四阶段调度详情"""
        # 1. 清洗阶段详情
        clean_details = {eq: [] for eq in range(self.num_clean_eq)}
        clean_machine_time = [0] * self.num_clean_eq
        workpiece_clean_end = {}
        for workpiece in solution['clean_order']:
            eq = solution['clean_eq'][workpiece]
            start = clean_machine_time[eq]
            end = start + self.clean_time
            clean_machine_time[eq] = end
            workpiece_clean_end[workpiece] = end
            clean_details[eq].append({'workpiece': workpiece, 'start': start, 'end': end})

        # 2. 充装阶段详情
        inflation_details = {eq: [] for eq in range(self.num_inflation_eq)}
        inflation_machine_time = [0] * self.num_inflation_eq
        workpiece_inflation_end = {}
        for workpiece in solution['inflation_order']:
            eq = solution['inflation_eq'][workpiece]
            start = max(inflation_machine_time[eq], workpiece_clean_end.get(workpiece, 0))
            end = start + self.inflation_time[workpiece]
            inflation_machine_time[eq] = end
            workpiece_inflation_end[workpiece] = end
            inflation_details[eq].append({'workpiece': workpiece, 'start': start, 'end': end})

        # 3. 摇匀阶段详情
        shake_details = {eq: [] for eq in range(self.num_shake_eq)}
        shake_machine_time = [0] * self.num_shake_eq
        workpiece_shake_end = {}
        for workpiece in solution['shake_order']:
            eq = solution['shake_eq'][workpiece]
            start = max(shake_machine_time[eq], workpiece_inflation_end.get(workpiece, 0))
            end = start + self.shake_time[workpiece]
            shake_machine_time[eq] = end
            workpiece_shake_end[workpiece] = end
            shake_details[eq].append({
                'workpiece': workpiece, 'start': start, 'end': end, 'group_count': self.num_components
            })

        # 4. 分析阶段详情
        analysis_details = {c: {eq: [] for eq in range(self.num_analysis_eq_per_component)}
                            for c in range(self.num_components)}
        analysis_machine_time = [[0] * self.num_analysis_eq_per_component for _ in range(self.num_components)]
        for workpiece in solution['analysis_order']:
            if workpiece < 0 or workpiece >= self.num_workpieces:
                continue
            start_analysis_time = workpiece_shake_end.get(workpiece, 0)
            group_test_order = solution['group_test_order'][workpiece]
            analysis_eq = solution['analysis_eq'][workpiece]

            for group_idx, group_id in enumerate(group_test_order):
                if group_idx < 0 or group_idx >= len(analysis_eq):
                    continue
                components_in_group = [j for j, g in enumerate(solution['component_groups'][workpiece]) if
                                       g == group_id]
                eq_for_group = analysis_eq[group_idx]
                if len(eq_for_group) != len(components_in_group):
                    eq_for_group = [random.randint(0, self.num_analysis_eq_per_component - 1) for _ in
                                    components_in_group]

                group_ready_time = start_analysis_time
                for comp_idx, component in enumerate(components_in_group):
                    if comp_idx < 0 or comp_idx >= len(eq_for_group):
                        continue
                    eq = eq_for_group[comp_idx]
                    group_ready_time = max(group_ready_time, analysis_machine_time[component][eq])

                max_analysis_time = max(
                    self.analysis_time[workpiece][component]
                    for comp_idx, component in enumerate(components_in_group)
                    if comp_idx < len(eq_for_group)
                ) if components_in_group else 0
                group_end_time = group_ready_time + max_analysis_time

                for comp_idx, component in enumerate(components_in_group):
                    if comp_idx < 0 or comp_idx >= len(eq_for_group):
                        continue
                    eq = eq_for_group[comp_idx]
                    analysis_machine_time[component][eq] = group_end_time
                    analysis_details[component][eq].append({
                        'workpiece': workpiece, 'start': group_ready_time, 'end': group_end_time,
                        'group': group_id, 'individual_time': self.analysis_time[workpiece][component]
                    })
                start_analysis_time = group_end_time

        return clean_details, inflation_details, shake_details, analysis_details

    def plot_gantt_chart(self, solution: Dict = None, title_suffix: str = ""):
        """上下结构甘特图：上方=清洗+充装+摇匀，下方=分析阶段"""
        if solution is None:
            solution = self.best_solution
        if solution is None:
            print(f"{self.name} 没有可用的调度方案进行绘制")
            return

        # 获取四阶段详情
        clean_details, inflation_details, shake_details, analysis_details = self.get_schedule_details(solution)
        colors = plt.cm.tab10(np.linspace(0, 1, self.num_workpieces))
        total_time = self.calculate_completion_time(solution)

        # 创建上下两个子图
        top_fig_height = (self.num_clean_eq + self.num_inflation_eq + self.num_shake_eq) * 0.8 + 2
        analysis_eq_total = self.num_components * self.num_analysis_eq_per_component
        bottom_fig_height = analysis_eq_total * 0.6 + 1
        fig, (ax_top, ax_bottom) = plt.subplots(
            2, 1, figsize=(16, top_fig_height + bottom_fig_height + 1),
            gridspec_kw={'height_ratios': [top_fig_height, bottom_fig_height]}
        )
        fig.suptitle(f'{self.name} 气体调度甘特图 {title_suffix}', fontsize=16, y=0.98)

        # 上方子图：绘制清洗+充装+摇匀
        y_base = 0
        stage_y_ranges = {}

        # 绘制清洗阶段
        stage_name = "清洗阶段"
        stage_eq_count = self.num_clean_eq
        stage_y_start = y_base + 1
        stage_y_end = stage_y_start + stage_eq_count
        stage_y_ranges[stage_name] = (stage_y_start, stage_y_end)

        for eq_idx, eq in enumerate(sorted(clean_details.keys())):
            y_pos = stage_y_start + eq_idx
            ax_top.text(-total_time * 0.02, y_pos, f'{stage_name} 设备{eq}',
                        ha='right', va='center', fontweight='bold', fontsize=9)
            for task in clean_details[eq]:
                ax_top.barh(
                    y_pos, task['end'] - task['start'], left=task['start'], height=0.6,
                    color=colors[task['workpiece']], edgecolor='black', alpha=0.9
                )
                ax_top.text(
                    task['start'] + (task['end'] - task['start']) / 2, y_pos,
                    f'瓶{task["workpiece"]}', ha='center', va='center',
                    color='white', fontweight='bold', fontsize=8
                )

        y_base = stage_y_end + 0.5

        # 绘制充装阶段
        stage_name = "充装阶段"
        stage_eq_count = self.num_inflation_eq
        stage_y_start = y_base + 1
        stage_y_end = stage_y_start + stage_eq_count
        stage_y_ranges[stage_name] = (stage_y_start, stage_y_end)

        for eq_idx, eq in enumerate(sorted(inflation_details.keys())):
            y_pos = stage_y_start + eq_idx
            ax_top.text(-total_time * 0.02, y_pos, f'{stage_name} 设备{eq}',
                        ha='right', va='center', fontweight='bold', fontsize=9)
            for task in inflation_details[eq]:
                ax_top.barh(
                    y_pos, task['end'] - task['start'], left=task['start'], height=0.6,
                    color=colors[task['workpiece']], edgecolor='black', alpha=0.9
                )
                ax_top.text(
                    task['start'] + (task['end'] - task['start']) / 2, y_pos,
                    f'瓶{task["workpiece"]}', ha='center', va='center',
                    color='white', fontweight='bold', fontsize=8
                )

        y_base = stage_y_end + 0.5

        # 绘制摇匀阶段
        stage_name = "摇匀阶段"
        stage_eq_count = self.num_shake_eq
        stage_y_start = y_base + 1
        stage_y_end = stage_y_start + stage_eq_count
        stage_y_ranges[stage_name] = (stage_y_start, stage_y_end)

        for eq_idx, eq in enumerate(sorted(shake_details.keys())):
            y_pos = stage_y_start + eq_idx
            ax_top.text(-total_time * 0.02, y_pos, f'{stage_name} 设备{eq}',
                        ha='right', va='center', fontweight='bold', fontsize=9)
            for task in shake_details[eq]:
                ax_top.barh(
                    y_pos, task['end'] - task['start'], left=task['start'], height=0.6,
                    color=colors[task['workpiece']], edgecolor='black', alpha=0.9
                )
                ax_top.text(
                    task['start'] + (task['end'] - task['start']) / 2, y_pos,
                    f'瓶{task["workpiece"]}\n({task["group_count"]}组分)',
                    ha='center', va='center', color='white', fontweight='bold', fontsize=7
                )

        # 上方子图样式调整
        ax_top.set_xlim(-total_time * 0.05, total_time * 1.1)
        ax_top.set_ylim(0, stage_y_end + 1)
        ax_top.set_yticks([])
        ax_top.set_xlabel('时间', fontsize=11)
        ax_top.set_title('上方：清洗 → 充装 → 摇匀 阶段（共3个前置阶段）', fontsize=12, pad=10)
        ax_top.grid(True, axis='x', linestyle='--', alpha=0.7)

        # 绘制阶段分隔线和标题
        for stage_name, (y_start, y_end) in stage_y_ranges.items():
            ax_top.axhline(y=y_start - 0.3, xmin=0, xmax=1, color='red', linestyle='--', alpha=0.7)
            ax_top.text(total_time * 0.5, y_start - 0.6, f'【{stage_name}】',
                        ha='center', va='center', fontweight='bold', color='red', fontsize=10)

        # 下方子图：绘制分析阶段
        y_pos_current = 1
        y_ticks = []
        y_tick_labels = []
        all_groups = {}

        for component in sorted(analysis_details.keys()):
            for eq in sorted(analysis_details[component].keys()):
                y_ticks.append(y_pos_current)
                y_tick_label = f'组分{component} 分析设备{eq}'
                y_tick_labels.append(y_tick_label)

                for task in analysis_details[component][eq]:
                    group_key = (task['workpiece'], task['group'])
                    if group_key not in all_groups:
                        all_groups[group_key] = []
                    all_groups[group_key].append((y_pos_current, task['start'], task['end']))

                    ax_bottom.barh(
                        y_pos_current, task['end'] - task['start'], left=task['start'], height=0.6,
                        color=colors[task['workpiece']], edgecolor='black', alpha=0.9
                    )
                    ax_bottom.text(
                        task['start'] + (task['end'] - task['start']) / 2, y_pos_current,
                        f'瓶{task["workpiece"]}\n({task["individual_time"]}s)',
                        ha='center', va='center', color='white', fontweight='bold', fontsize=7
                    )

                y_pos_current += 1
            y_pos_current += 0.5

        # 绘制串联组连接线
        for (workpiece, group_id), tasks in all_groups.items():
            if len(tasks) > 1:
                mid_time = (tasks[0][1] + tasks[0][2]) / 2
                y_min = min([t[0] for t in tasks]) - 0.3
                y_max = max([t[0] for t in tasks]) + 0.3
                ax_bottom.plot(
                    [mid_time, mid_time], [y_min, y_max],
                    'k--', linewidth=1.5, alpha=0.7
                )
                ax_bottom.text(
                    mid_time, y_max + 0.2, f'串联组{group_id}',
                    ha='center', va='bottom', color='black', fontsize=7, fontweight='bold'
                )

        # 下方子图样式调整
        ax_bottom.set_xlim(-total_time * 0.05, total_time * 1.1)
        ax_bottom.set_ylim(0, y_pos_current + 1)
        ax_bottom.set_yticks(y_ticks)
        ax_bottom.set_yticklabels(y_tick_labels, fontsize=9)
        ax_bottom.set_xlabel('时间', fontsize=11)
        ax_bottom.set_title('下方：分析阶段（串联组用黑色虚线连接）', fontsize=12, pad=10)
        ax_bottom.grid(True, axis='x', linestyle='--', alpha=0.7)

        # 添加全局图例
        legend_items = [mpatches.Patch(color=colors[i], label=f'气瓶 {i}')
                        for i in range(min(10, self.num_workpieces))]
        if self.num_workpieces > 10:
            legend_items.append(mpatches.Patch(color='white', label=f'... 共{self.num_workpieces}个气瓶'))
        legend_items.append(mpatches.Patch(color='red', linestyle='--', label='阶段分隔线'))
        legend_items.append(mpatches.Patch(color='black', linestyle='--', label='分析串联组'))

        fig.legend(
            handles=legend_items, loc='lower center', ncol=6,
            bbox_to_anchor=(0.5, 0.02), fontsize=10
        )

        plt.tight_layout(rect=[0, 0.08, 1, 0.96])
        plt.show()

    def optimize(self):
        raise NotImplementedError("子类必须实现优化方法")

    def get_results(self) -> Dict:
        """返回算法运行结果，用于保存到文件"""
        return {
            'algorithm': self.name,
            'best_time': self.best_time,
            'execution_time': self.execution_time,
            'num_workpieces': self.num_workpieces,
            'num_components': self.num_components,
            'max_iter': self.max_iter,
            'timestamp': datetime.now().strftime("%Y-%m-%d %H:%M:%S")
        }


class GeneticAlgorithm(BaseSchedulingAlgorithm):
    """遗传算法（多设备适配）"""

    def __init__(self,
                 instance: Dict,
                 population_size: int = 50,
                 generations: int = 100,
                 crossover_rate: float = 0.8,
                 mutation_rate: float = 0.1,
                 name: str = "遗传算法(GA)"):
        super().__init__(instance, generations, name)
        self.population_size = population_size
        self.crossover_rate = crossover_rate
        self.mutation_rate = mutation_rate
        self.population = []

    def initialize_population(self):
        self.population = [self.initialize_solution() for _ in range(self.population_size)]

    def select_parents(self, fitness_values: List[float]) -> Tuple[Dict, Dict]:
        total_fitness = sum(fitness_values)
        probabilities = [f / total_fitness for f in fitness_values]
        parent1_idx = np.random.choice(self.population_size, p=probabilities)
        parent2_idx = np.random.choice(self.population_size, p=probabilities)
        while parent1_idx == parent2_idx:
            parent2_idx = np.random.choice(self.population_size, p=probabilities)
        return self.population[parent1_idx], self.population[parent2_idx]

    def crossover(self, parent1: Dict, parent2: Dict) -> Tuple[Dict, Dict]:
        if random.random() > self.crossover_rate:
            return parent1.copy(), parent2.copy()

        def order_crossover(order1, order2):
            size = len(order1)
            a, b = random.sample(range(size), 2)
            if a > b:
                a, b = b, a
            child1, child2 = [-1] * size, [-1] * size
            child1[a:b + 1] = order1[a:b + 1]
            child2[a:b + 1] = order2[a:b + 1]

            def fill_child(child, parent, start, end):
                ptr = (end + 1) % size
                for i in range(end + 1, end + 1 + size):
                    current = parent[i % size]
                    if current not in child:
                        child[ptr] = current
                        ptr = (ptr + 1) % size
                return child

            return fill_child(child1, order2, a, b), fill_child(child2, order1, a, b)

        # 交叉所有阶段顺序
        child1_clean, child2_clean = order_crossover(parent1['clean_order'], parent2['clean_order'])
        child1_inflate, child2_inflate = order_crossover(parent1['inflation_order'], parent2['inflation_order'])
        child1_shake, child2_shake = order_crossover(parent1['shake_order'], parent2['shake_order'])
        child1_analysis, child2_analysis = order_crossover(parent1['analysis_order'], parent2['analysis_order'])

        # 交叉设备分配
        child1_clean_eq = parent1['clean_eq'].copy()
        child2_clean_eq = parent2['clean_eq'].copy()
        child1_shake_eq = parent1['shake_eq'].copy()
        child2_shake_eq = parent2['shake_eq'].copy()
        # 50%概率交换部分设备分配
        for i in range(self.num_workpieces):
            if random.random() < 0.5:
                child1_clean_eq[i], child2_clean_eq[i] = child2_clean_eq[i], child1_clean_eq[i]
                child1_shake_eq[i], child2_shake_eq[i] = child2_shake_eq[i], child1_shake_eq[i]

        # 构建子染色体
        child1 = {
            'clean_order': child1_clean, 'clean_eq': child1_clean_eq,
            'inflation_order': child1_inflate, 'inflation_eq': parent1['inflation_eq'].copy(),
            'shake_order': child1_shake, 'shake_eq': child1_shake_eq,
            'analysis_order': child1_analysis,
            'component_groups': [g.copy() for g in parent1['component_groups']],
            'group_test_order': [g.copy() for g in parent1['group_test_order']],
            'analysis_eq': [g.copy() for g in parent1['analysis_eq']]
        }
        for i in range(len(child1['analysis_eq'])):
            child1['analysis_eq'][i] = [e.copy() for e in child1['analysis_eq'][i]]

        child2 = {
            'clean_order': child2_clean, 'clean_eq': child2_clean_eq,
            'inflation_order': child2_inflate, 'inflation_eq': parent2['inflation_eq'].copy(),
            'shake_order': child2_shake, 'shake_eq': child2_shake_eq,
            'analysis_order': child2_analysis,
            'component_groups': [g.copy() for g in parent2['component_groups']],
            'group_test_order': [g.copy() for g in parent2['group_test_order']],
            'analysis_eq': [g.copy() for g in parent2['analysis_eq']]
        }
        for i in range(len(child2['analysis_eq'])):
            child2['analysis_eq'][i] = [e.copy() for e in child2['analysis_eq'][i]]

        # 组分分组交叉
        for i in range(self.num_workpieces):
            if random.random() < 0.5:
                child1['inflation_eq'][i] = parent2['inflation_eq'][i]
                child2['inflation_eq'][i] = parent1['inflation_eq'][i]

        for i in range(self.num_workpieces):
            if random.random() < 0.5:
                child1['component_groups'][i] = parent2['component_groups'][i].copy()
                groups1 = child1['component_groups'][i]
                unique_groups1 = list(sorted(set(groups1)))
                random.shuffle(unique_groups1)
                child1['group_test_order'][i] = unique_groups1
                new_eq1 = []
                for group_id in unique_groups1:
                    components = [j for j, g in enumerate(groups1) if g == group_id]
                    new_eq1.append([random.randint(0, self.num_analysis_eq_per_component - 1) for _ in components])
                child1['analysis_eq'][i] = new_eq1

                child2['component_groups'][i] = parent1['component_groups'][i].copy()
                groups2 = child2['component_groups'][i]
                unique_groups2 = list(sorted(set(groups2)))
                random.shuffle(unique_groups2)
                child2['group_test_order'][i] = unique_groups2
                new_eq2 = []
                for group_id in unique_groups2:
                    components = [j for j, g in enumerate(groups2) if g == group_id]
                    new_eq2.append([random.randint(0, self.num_analysis_eq_per_component - 1) for _ in components])
                child2['analysis_eq'][i] = new_eq2

        return child1, child2

    def mutate(self, chromosome: Dict) -> Dict:
        mutated = {
            'clean_order': chromosome['clean_order'].copy(),
            'clean_eq': chromosome['clean_eq'].copy(),
            'inflation_order': chromosome['inflation_order'].copy(),
            'inflation_eq': chromosome['inflation_eq'].copy(),
            'shake_order': chromosome['shake_order'].copy(),
            'shake_eq': chromosome['shake_eq'].copy(),
            'analysis_order': chromosome['analysis_order'].copy(),
            'component_groups': [g.copy() for g in chromosome['component_groups']],
            'group_test_order': [g.copy() for g in chromosome['group_test_order']],
            'analysis_eq': [g.copy() for g in chromosome['analysis_eq']]
        }
        for i in range(len(mutated['analysis_eq'])):
            mutated['analysis_eq'][i] = [e.copy() for e in mutated['analysis_eq'][i]]

        # 顺序变异
        if random.random() < self.mutation_rate:
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            mutated['clean_order'][idx1], mutated['clean_order'][idx2] = mutated['clean_order'][idx2], \
                mutated['clean_order'][idx1]
        if random.random() < self.mutation_rate:
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            mutated['inflation_order'][idx1], mutated['inflation_order'][idx2] = mutated['inflation_order'][idx2], \
                mutated['inflation_order'][idx1]
        if random.random() < self.mutation_rate:
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            mutated['shake_order'][idx1], mutated['shake_order'][idx2] = mutated['shake_order'][idx2], \
                mutated['shake_order'][idx1]
        if random.random() < self.mutation_rate:
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            mutated['analysis_order'][idx1], mutated['analysis_order'][idx2] = mutated['analysis_order'][idx2], \
                mutated['analysis_order'][idx1]

        # 设备分配变异（多设备适配）
        for i in range(self.num_workpieces):
            if random.random() < self.mutation_rate * 0.5:
                mutated['clean_eq'][i] = random.randint(0, self.num_clean_eq - 1)
            if random.random() < self.mutation_rate * 0.5:
                mutated['shake_eq'][i] = random.randint(0, self.num_shake_eq - 1)
            if random.random() < self.mutation_rate:
                mutated['inflation_eq'][i] = random.randint(0, self.num_inflation_eq - 1)

        # 组分分组变异
        for i in range(self.num_workpieces):
            if random.random() < self.mutation_rate:
                comp_idx = random.randint(0, self.num_components - 1)
                current_groups = mutated['component_groups'][i]
                possible_groups = list(set(current_groups))
                if len(possible_groups) == 1:
                    new_group = 1 if possible_groups[0] == 0 else 0
                else:
                    new_group = random.choice([g for g in possible_groups if g != current_groups[comp_idx]])
                current_groups[comp_idx] = new_group
                unique_groups = list(sorted(set(current_groups)))
                random.shuffle(unique_groups)
                mutated['group_test_order'][i] = unique_groups
                new_analysis_eq = []
                for group_id in unique_groups:
                    components_in_group = [j for j, g in enumerate(current_groups) if g == group_id]
                    new_analysis_eq.append(
                        [random.randint(0, self.num_analysis_eq_per_component - 1) for _ in components_in_group])
                mutated['analysis_eq'][i] = new_analysis_eq

        for i in range(self.num_workpieces):
            for group_idx in range(len(mutated['group_test_order'][i])):
                if random.random() < self.mutation_rate:
                    eq_list = mutated['analysis_eq'][i][group_idx]
                    if len(eq_list) > 0:
                        comp_idx = random.randint(0, len(eq_list) - 1)
                        eq_list[comp_idx] = random.randint(0, self.num_analysis_eq_per_component - 1)

        return mutated

    def optimize(self) -> Tuple[Dict, float]:
        start_time = time.time()  # 记录开始时间

        self.initialize_population()
        self.iteration_best_times = []
        self.best_time = float('inf')
        self.best_solution = None

        for generation in range(self.max_iter):
            try:
                completion_times = [self.calculate_completion_time(chrom) for chrom in self.population]
                fitness_values = [1.0 / time for time in completion_times]
            except Exception as e:
                print(f"{self.name} 计算适应度时出错: {e}")
                self.initialize_population()
                completion_times = [self.calculate_completion_time(chrom) for chrom in self.population]
                fitness_values = [1.0 / time for time in completion_times]

            current_best_idx = np.argmin(completion_times)
            current_best_time = completion_times[current_best_idx]
            current_best_solution = self.population[current_best_idx]

            self.iteration_best_times.append(current_best_time)

            if current_best_time < self.best_time:
                self.best_time = current_best_time
                self.best_solution = current_best_solution

            if generation % 10 == 0:
                print(f"{self.name} 第 {generation} 代: 最佳完成时间 = {current_best_time:.2f}")

            new_population = []
            elite_size = max(1, int(self.population_size * 0.1))
            elite_indices = np.argsort(completion_times)[:elite_size]
            for idx in elite_indices:
                new_population.append(self.population[idx])

            while len(new_population) < self.population_size:
                parent1, parent2 = self.select_parents(fitness_values)
                child1, child2 = self.crossover(parent1, parent2)
                child1 = self.mutate(child1)
                child2 = self.mutate(child2)
                new_population.append(child1)
                if len(new_population) < self.population_size:
                    new_population.append(child2)

            self.population = new_population

        # 记录执行时间
        self.execution_time = time.time() - start_time

        return self.best_solution, self.best_time


class ParticleSwarmOptimization(BaseSchedulingAlgorithm):
    """粒子群优化（多设备适配）"""

    def __init__(self,
                 instance: Dict,
                 swarm_size: int = 50,
                 max_iter: int = 100,
                 w: float = 0.7,
                 c1: float = 1.5,
                 c2: float = 1.5,
                 name: str = "粒子群优化(PSO)"):
        super().__init__(instance, max_iter, name)
        self.swarm_size = swarm_size
        self.w = w
        self.c1 = c1
        self.c2 = c2
        self.swarm = []
        self.pbest = []
        self.pbest_times = []

    def initialize_swarm(self):
        self.swarm = [self.initialize_solution() for _ in range(self.swarm_size)]
        self.pbest = [s.copy() for s in self.swarm]
        self.pbest_times = [self.calculate_completion_time(s) for s in self.pbest]
        best_idx = np.argmin(self.pbest_times)
        self.best_time = self.pbest_times[best_idx]
        self.best_solution = self.pbest[best_idx].copy()

    def update_particle(self, particle: Dict, pbest: Dict, gbest: Dict) -> Dict:
        new_particle = {
            'clean_order': particle['clean_order'].copy(),
            'clean_eq': particle['clean_eq'].copy(),
            'inflation_order': particle['inflation_order'].copy(),
            'inflation_eq': particle['inflation_eq'].copy(),
            'shake_order': particle['shake_order'].copy(),
            'shake_eq': particle['shake_eq'].copy(),
            'analysis_order': particle['analysis_order'].copy(),
            'component_groups': [g.copy() for g in particle['component_groups']],
            'group_test_order': [g.copy() for g in particle['group_test_order']],
            'analysis_eq': [g.copy() for g in particle['analysis_eq']]
        }
        for i in range(len(new_particle['analysis_eq'])):
            new_particle['analysis_eq'][i] = [e.copy() for e in new_particle['analysis_eq'][i]]

        # 向pbest学习
        if random.random() < self.c1 / (self.c1 + self.c2):
            if random.random() < 0.3:
                new_particle['clean_order'] = pbest['clean_order'].copy()
                new_particle['clean_eq'] = pbest['clean_eq'].copy()
            if random.random() < 0.3:
                new_particle['shake_order'] = pbest['shake_order'].copy()
                new_particle['shake_eq'] = pbest['shake_eq'].copy()
            if random.random() < 0.4:
                new_particle['inflation_order'] = pbest['inflation_order'].copy()
                new_particle['inflation_eq'] = pbest['inflation_eq'].copy()
                new_particle['analysis_order'] = pbest['analysis_order'].copy()

        # 向gbest学习
        if random.random() < self.c2 / (self.c1 + self.c2):
            if random.random() < 0.3:
                new_particle['clean_order'] = gbest['clean_order'].copy()
                new_particle['clean_eq'] = gbest['clean_eq'].copy()
            if random.random() < 0.3:
                new_particle['shake_order'] = gbest['shake_order'].copy()
                new_particle['shake_eq'] = gbest['shake_eq'].copy()
            if random.random() < 0.4:
                new_particle['inflation_order'] = gbest['inflation_order'].copy()
                new_particle['inflation_eq'] = gbest['inflation_eq'].copy()
                new_particle['analysis_order'] = gbest['analysis_order'].copy()

            for i in range(self.num_workpieces):
                if random.random() < 0.2:
                    new_particle['component_groups'][i] = gbest['component_groups'][i].copy()
                    groups = new_particle['component_groups'][i]
                    unique_groups = list(sorted(set(groups)))
                    random.shuffle(unique_groups)
                    new_particle['group_test_order'][i] = unique_groups
                    new_eq = []
                    for group_id in unique_groups:
                        components = [j for j, g in enumerate(groups) if g == group_id]
                        new_eq.append([random.randint(0, self.num_analysis_eq_per_component - 1) for _ in components])
                    new_particle['analysis_eq'][i] = new_eq

        # 随机变异
        if random.random() < self.w:
            if random.random() < 0.2:
                idx = random.randint(0, self.num_workpieces - 1)
                new_particle['clean_eq'][idx] = random.randint(0, self.num_clean_eq - 1)
            if random.random() < 0.2:
                idx = random.randint(0, self.num_workpieces - 1)
                new_particle['shake_eq'][idx] = random.randint(0, self.num_shake_eq - 1)
            if random.random() < 0.4:
                idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                new_particle['inflation_order'][idx1], new_particle['inflation_order'][idx2] = \
                    new_particle['inflation_order'][idx2], new_particle['inflation_order'][idx1]
            if random.random() < 0.4:
                idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                new_particle['analysis_order'][idx1], new_particle['analysis_order'][idx2] = \
                    new_particle['analysis_order'][idx2], new_particle['analysis_order'][idx1]
            if random.random() < 0.3:
                idx = random.randint(0, self.num_workpieces - 1)
                new_particle['inflation_eq'][idx] = random.randint(0, self.num_inflation_eq - 1)

        return new_particle

    def optimize(self) -> Tuple[Dict, float]:
        start_time = time.time()  # 记录开始时间

        self.initialize_swarm()
        self.iteration_best_times = []
        for iter in range(self.max_iter):
            for i in range(self.swarm_size):
                new_particle = self.update_particle(self.swarm[i], self.pbest[i], self.best_solution)
                new_time = self.calculate_completion_time(new_particle)
                if new_time < self.pbest_times[i]:
                    self.pbest[i] = new_particle.copy()
                    self.pbest_times[i] = new_time
                    if new_time < self.best_time:
                        self.best_time = new_time
                        self.best_solution = new_particle.copy()
            self.iteration_best_times.append(self.best_time)
            if iter % 10 == 0:
                print(f"{self.name} 第 {iter} 代: 最佳完成时间 = {self.best_time:.2f}")
            self.w = self.w * 0.99

        # 记录执行时间
        self.execution_time = time.time() - start_time

        return self.best_solution, self.best_time


class SimulatedAnnealing(BaseSchedulingAlgorithm):
    """模拟退火（多设备适配）"""

    def __init__(self,
                 instance: Dict,
                 init_temp: float = 100.0,
                 cool_rate: float = 0.95,
                 max_iter: int = 100,
                 name: str = "模拟退火(SA)"):
        super().__init__(instance, max_iter, name)
        self.init_temp = init_temp
        self.cool_rate = cool_rate
        self.current_solution = None
        self.current_time = float('inf')

    def generate_neighbor(self, solution: Dict) -> Dict:
        new_solution = {
            'clean_order': solution['clean_order'].copy(),
            'clean_eq': solution['clean_eq'].copy(),
            'inflation_order': solution['inflation_order'].copy(),
            'inflation_eq': solution['inflation_eq'].copy(),
            'shake_order': solution['shake_order'].copy(),
            'shake_eq': solution['shake_eq'].copy(),
            'analysis_order': solution['analysis_order'].copy(),
            'component_groups': [g.copy() for g in solution['component_groups']],
            'group_test_order': [g.copy() for g in solution['group_test_order']],
            'analysis_eq': [g.copy() for g in solution['analysis_eq']]
        }
        for i in range(len(new_solution['analysis_eq'])):
            new_solution['analysis_eq'][i] = [e.copy() for e in new_solution['analysis_eq'][i]]

        # 变异类型（多设备适配）
        mutation_type = random.choice([
            'clean_order', 'clean_eq', 'shake_order', 'shake_eq',
            'inflation_order', 'inflation_eq', 'analysis_order', 'group'
        ])

        if mutation_type == 'clean_order':
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            new_solution['clean_order'][idx1], new_solution['clean_order'][idx2] = new_solution['clean_order'][idx2], \
                new_solution['clean_order'][idx1]
        elif mutation_type == 'clean_eq':
            idx = random.randint(0, self.num_workpieces - 1)
            new_solution['clean_eq'][idx] = random.randint(0, self.num_clean_eq - 1)
        elif mutation_type == 'shake_order':
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            new_solution['shake_order'][idx1], new_solution['shake_order'][idx2] = new_solution['shake_order'][idx2], \
                new_solution['shake_order'][idx1]
        elif mutation_type == 'shake_eq':
            idx = random.randint(0, self.num_workpieces - 1)
            new_solution['shake_eq'][idx] = random.randint(0, self.num_shake_eq - 1)
        elif mutation_type == 'inflation_order':
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            new_solution['inflation_order'][idx1], new_solution['inflation_order'][idx2] = \
                new_solution['inflation_order'][idx2], new_solution['inflation_order'][idx1]
        elif mutation_type == 'inflation_eq':
            idx = random.randint(0, self.num_workpieces - 1)
            new_solution['inflation_eq'][idx] = random.randint(0, self.num_inflation_eq - 1)
        elif mutation_type == 'analysis_order':
            idx1, idx2 = random.sample(range(self.num_workpieces), 2)
            new_solution['analysis_order'][idx1], new_solution['analysis_order'][idx2] = new_solution['analysis_order'][
                idx2], new_solution['analysis_order'][idx1]
        elif mutation_type == 'group':
            wp_idx = random.randint(0, self.num_workpieces - 1)
            comp_idx = random.randint(0, self.num_components - 1)
            current_groups = new_solution['component_groups'][wp_idx]
            possible_groups = list(set(current_groups))
            if len(possible_groups) == 1:
                new_group = 1 if possible_groups[0] == 0 else 0
            else:
                new_group = random.choice([g for g in possible_groups if g != current_groups[comp_idx]])
            current_groups[comp_idx] = new_group
            unique_groups = list(sorted(set(current_groups)))
            random.shuffle(unique_groups)
            new_solution['group_test_order'][wp_idx] = unique_groups
            new_analysis_eq = []
            for group_id in unique_groups:
                components_in_group = [j for j, g in enumerate(current_groups) if g == group_id]
                new_analysis_eq.append(
                    [random.randint(0, self.num_analysis_eq_per_component - 1) for _ in components_in_group])
            new_solution['analysis_eq'][wp_idx] = new_analysis_eq

        return new_solution

    def optimize(self) -> Tuple[Dict, float]:
        start_time = time.time()  # 记录开始时间

        self.current_solution = self.initialize_solution()
        self.current_time = self.calculate_completion_time(self.current_solution)
        self.best_solution = self.current_solution.copy()
        self.best_time = self.current_time
        self.iteration_best_times = []
        temp = self.init_temp

        for iter in range(self.max_iter):
            neighbor = self.generate_neighbor(self.current_solution)
            neighbor_time = self.calculate_completion_time(neighbor)
            delta = self.current_time - neighbor_time

            if delta > 0:
                self.current_solution = neighbor
                self.current_time = neighbor_time
            else:
                prob = np.exp(delta / temp)
                if random.random() < prob:
                    self.current_solution = neighbor
                    self.current_time = neighbor_time

            if self.current_time < self.best_time:
                self.best_time = self.current_time
                self.best_solution = self.current_solution.copy()

            self.iteration_best_times.append(self.best_time)
            temp *= self.cool_rate

            if iter % 10 == 0:
                print(f"{self.name} 第 {iter} 代: 最佳完成时间 = {self.best_time:.2f}")

        # 记录执行时间
        self.execution_time = time.time() - start_time

        return self.best_solution, self.best_time


class TabuSearch(BaseSchedulingAlgorithm):
    """带可消融策略的改进禁忌搜索（多设备适配）"""

    def __init__(self,
                 instance: Dict,
                 population_size: int = 100,
                 tabu_size: int = 20,
                 neighborhood_size: int = 10,
                 max_iter: int = 100,
                 # 策略开关参数
                 use_elite_protection: bool = True,
                 dynamic_tabu_length: bool = True,
                 diverse_perturbation: bool = True,
                 history_heuristic: bool = True,
                 name: str = "改进禁忌搜索(TS)"):
        super().__init__(instance, max_iter, name)
        self.population_size = population_size
        self.base_tabu_size = tabu_size
        self.tabu_size = tabu_size
        self.neighborhood_size = neighborhood_size
        self.tabu_list = []
        self.current_population = []

        # 策略开关
        self.use_elite_protection = use_elite_protection
        self.dynamic_tabu_length = dynamic_tabu_length
        self.diverse_perturbation = diverse_perturbation
        self.history_heuristic = history_heuristic

        # 历史信息记录
        self.history_best_times = []
        self.mutation_effectiveness = {}
        self.elite_pool = []
        self.elite_size = max(1, int(population_size * 0.1))

    def solution_hash(self, solution: Dict) -> int:
        """生成解的哈希值用于禁忌判断"""
        return hash(
            tuple(solution['clean_order']) + tuple(solution['clean_eq']) +
            tuple(solution['shake_order']) + tuple(solution['shake_eq']) +
            tuple(solution['inflation_order']) + tuple(solution['inflation_eq']) +
            tuple(solution['analysis_order'])
        )

    def generate_neighborhood(self, solution: Dict) -> List[Dict]:
        """生成邻域解（支持多样化扰动策略）"""
        neighborhood = []

        # 多样化扰动：根据历史效果调整变异类型概率
        if self.diverse_perturbation and self.mutation_effectiveness:
            avg_effect = {k: v['total'] / v['count'] for k, v in self.mutation_effectiveness.items() if v['count'] > 0}
            total = sum(avg_effect.values())
            if total > 0:
                mutation_probs = {k: v / total for k, v in avg_effect.items()}
            else:
                mutation_probs = None
        else:
            mutation_probs = None

        for _ in range(self.neighborhood_size):
            # 复制原始解
            new_solution = {
                'clean_order': solution['clean_order'].copy(),
                'clean_eq': solution['clean_eq'].copy(),
                'inflation_order': solution['inflation_order'].copy(),
                'inflation_eq': solution['inflation_eq'].copy(),
                'shake_order': solution['shake_order'].copy(),
                'shake_eq': solution['shake_eq'].copy(),
                'analysis_order': solution['analysis_order'].copy(),
                'component_groups': [g.copy() for g in solution['component_groups']],
                'group_test_order': [g.copy() for g in solution['group_test_order']],
                'analysis_eq': [g.copy() for g in solution['analysis_eq']]
            }
            # 深层复制分析设备分配
            for i in range(len(new_solution['analysis_eq'])):
                new_solution['analysis_eq'][i] = [e.copy() for e in new_solution['analysis_eq'][i]]

            # 选择变异类型
            mutation_types = [
                'clean_order', 'clean_eq', 'shake_order', 'shake_eq',
                'inflation_order', 'inflation_eq', 'analysis_order', 'group'
            ]
            if mutation_probs:
                mutation_type = random.choices(
                    mutation_types,
                    weights=[mutation_probs.get(t, 0.1) for t in mutation_types]
                )[0]
            else:
                mutation_type = random.choice(mutation_types)

            # 执行变异操作
            if mutation_type == 'clean_order':
                idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                new_solution['clean_order'][idx1], new_solution['clean_order'][idx2] = new_solution['clean_order'][
                    idx2], new_solution['clean_order'][idx1]
            elif mutation_type == 'clean_eq':
                idx = random.randint(0, self.num_workpieces - 1)
                new_solution['clean_eq'][idx] = random.randint(0, self.num_clean_eq - 1)
            elif mutation_type == 'shake_order':
                idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                new_solution['shake_order'][idx1], new_solution['shake_order'][idx2] = new_solution['shake_order'][
                    idx2], new_solution['shake_order'][idx1]
            elif mutation_type == 'shake_eq':
                idx = random.randint(0, self.num_workpieces - 1)
                new_solution['shake_eq'][idx] = random.randint(0, self.num_shake_eq - 1)
            elif mutation_type == 'inflation_order':
                idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                new_solution['inflation_order'][idx1], new_solution['inflation_order'][idx2] = \
                new_solution['inflation_order'][idx2], new_solution['inflation_order'][idx1]
            elif mutation_type == 'inflation_eq':
                idx = random.randint(0, self.num_workpieces - 1)
                new_solution['inflation_eq'][idx] = random.randint(0, self.num_inflation_eq - 1)
            elif mutation_type == 'analysis_order':
                idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                new_solution['analysis_order'][idx1], new_solution['analysis_order'][idx2] = \
                new_solution['analysis_order'][idx2], new_solution['analysis_order'][idx1]
            elif mutation_type == 'group':
                wp_idx = random.randint(0, self.num_workpieces - 1)
                comp_idx = random.randint(0, self.num_components - 1)
                current_groups = new_solution['component_groups'][wp_idx]
                possible_groups = list(set(current_groups))
                if len(possible_groups) == 1:
                    new_group = 1 if possible_groups[0] == 0 else 0
                else:
                    new_group = random.choice([g for g in possible_groups if g != current_groups[comp_idx]])
                current_groups[comp_idx] = new_group
                unique_groups = list(sorted(set(current_groups)))
                random.shuffle(unique_groups)
                new_solution['group_test_order'][wp_idx] = unique_groups
                new_analysis_eq = []
                for group_id in unique_groups:
                    components_in_group = [j for j, g in enumerate(current_groups) if g == group_id]
                    new_analysis_eq.append(
                        [random.randint(0, self.num_analysis_eq_per_component - 1) for _ in components_in_group])
                new_solution['analysis_eq'][wp_idx] = new_analysis_eq

            neighborhood.append(new_solution)

        return neighborhood

    def optimize(self) -> Tuple[Dict, float]:
        start_time = time.time()  # 记录开始时间

        self.current_population = [self.initialize_solution() for _ in range(self.population_size)]
        self.best_time = float('inf')
        self.best_solution = None
        self.iteration_best_times = []
        self.tabu_list = []
        self.elite_pool = []

        # 初始化变异效果记录
        self.mutation_effectiveness = {
            'clean_order': {'total': 0, 'count': 0},
            'clean_eq': {'total': 0, 'count': 0},
            'shake_order': {'total': 0, 'count': 0},
            'shake_eq': {'total': 0, 'count': 0},
            'inflation_order': {'total': 0, 'count': 0},
            'inflation_eq': {'total': 0, 'count': 0},
            'analysis_order': {'total': 0, 'count': 0},
            'group': {'total': 0, 'count': 0}
        }

        for iter in range(self.max_iter):
            # 动态禁忌长度调整
            if self.dynamic_tabu_length and iter > 0 and iter % 10 == 0:
                if len(self.history_best_times) >= 10:
                    recent_improve = self.history_best_times[-10] - self.history_best_times[-1]
                    if recent_improve < 0.05 * self.history_best_times[-10]:
                        self.tabu_size = min(int(self.base_tabu_size * 1.5), self.population_size * 2)
                    elif recent_improve > 0.2 * self.history_best_times[-10]:
                        self.tabu_size = max(int(self.base_tabu_size * 0.5), 5)
                    else:
                        self.tabu_size = self.base_tabu_size

            # 生成所有候选解及对应的变异类型
            all_candidates = []
            for solution in self.current_population:
                for _ in range(self.neighborhood_size):
                    # 选择变异类型
                    mutation_types = [
                        'clean_order', 'clean_eq', 'shake_order', 'shake_eq',
                        'inflation_order', 'inflation_eq', 'analysis_order', 'group'
                    ]
                    mutation_type = random.choice(mutation_types)

                    # 复制解
                    new_solution = {
                        'clean_order': solution['clean_order'].copy(),
                        'clean_eq': solution['clean_eq'].copy(),
                        'inflation_order': solution['inflation_order'].copy(),
                        'inflation_eq': solution['inflation_eq'].copy(),
                        'shake_order': solution['shake_order'].copy(),
                        'shake_eq': solution['shake_eq'].copy(),
                        'analysis_order': solution['analysis_order'].copy(),
                        'component_groups': [g.copy() for g in solution['component_groups']],
                        'group_test_order': [g.copy() for g in solution['group_test_order']],
                        'analysis_eq': [g.copy() for g in solution['analysis_eq']]
                    }
                    # 深层复制分析设备分配
                    for i in range(len(new_solution['analysis_eq'])):
                        new_solution['analysis_eq'][i] = [e.copy() for e in new_solution['analysis_eq'][i]]

                    # 执行变异
                    if mutation_type == 'clean_order':
                        idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                        new_solution['clean_order'][idx1], new_solution['clean_order'][idx2] = \
                        new_solution['clean_order'][idx2], new_solution['clean_order'][idx1]
                    elif mutation_type == 'clean_eq':
                        idx = random.randint(0, self.num_workpieces - 1)
                        new_solution['clean_eq'][idx] = random.randint(0, self.num_clean_eq - 1)
                    elif mutation_type == 'shake_order':
                        idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                        new_solution['shake_order'][idx1], new_solution['shake_order'][idx2] = \
                        new_solution['shake_order'][idx2], new_solution['shake_order'][idx1]
                    elif mutation_type == 'shake_eq':
                        idx = random.randint(0, self.num_workpieces - 1)
                        new_solution['shake_eq'][idx] = random.randint(0, self.num_shake_eq - 1)
                    elif mutation_type == 'inflation_order':
                        idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                        new_solution['inflation_order'][idx1], new_solution['inflation_order'][idx2] = \
                        new_solution['inflation_order'][idx2], new_solution['inflation_order'][idx1]
                    elif mutation_type == 'inflation_eq':
                        idx = random.randint(0, self.num_workpieces - 1)
                        new_solution['inflation_eq'][idx] = random.randint(0, self.num_inflation_eq - 1)
                    elif mutation_type == 'analysis_order':
                        idx1, idx2 = random.sample(range(self.num_workpieces), 2)
                        new_solution['analysis_order'][idx1], new_solution['analysis_order'][idx2] = \
                        new_solution['analysis_order'][idx2], new_solution['analysis_order'][idx1]
                    elif mutation_type == 'group':
                        wp_idx = random.randint(0, self.num_workpieces - 1)
                        comp_idx = random.randint(0, self.num_components - 1)
                        current_groups = new_solution['component_groups'][wp_idx]
                        possible_groups = list(set(current_groups))
                        if len(possible_groups) == 1:
                            new_group = 1 if possible_groups[0] == 0 else 0
                        else:
                            new_group = random.choice([g for g in possible_groups if g != current_groups[comp_idx]])
                        current_groups[comp_idx] = new_group
                        unique_groups = list(sorted(set(current_groups)))
                        random.shuffle(unique_groups)
                        new_solution['group_test_order'][wp_idx] = unique_groups
                        new_analysis_eq = []
                        for group_id in unique_groups:
                            components_in_group = [j for j, g in enumerate(current_groups) if g == group_id]
                            new_analysis_eq.append([random.randint(0, self.num_analysis_eq_per_component - 1) for _ in
                                                    components_in_group])
                        new_solution['analysis_eq'][wp_idx] = new_analysis_eq

                    all_candidates.append((new_solution, mutation_type))

            # 初始化候选解列表，确保即使没有有效解也不会报错
            candidate_with_time = []
            seen_hashes = set()

            # 去重并计算时间
            for candidate, mutation_type in all_candidates:
                candidate_hash = self.solution_hash(candidate)
                if candidate_hash not in seen_hashes:
                    seen_hashes.add(candidate_hash)
                    try:
                        t = self.calculate_completion_time(candidate)
                        candidate_with_time.append((candidate, t, candidate_hash, mutation_type))
                    except Exception as e:
                        print(f"计算候选解时间出错: {e}")

            # 如果没有有效候选解，生成新解作为备选
            if not candidate_with_time:
                print(f"警告：第 {iter} 代未生成有效候选解，使用随机解替代")
                for _ in range(self.neighborhood_size):
                    new_sol = self.initialize_solution()
                    try:
                        t = self.calculate_completion_time(new_sol)
                        candidate_with_time.append((new_sol, t, self.solution_hash(new_sol), "random"))
                    except Exception as e:
                        print(f"生成随机解出错: {e}")

            # 历史信息启发式排序
            if self.history_heuristic and len(self.history_best_times) > 0 and candidate_with_time:
                current_best = self.history_best_times[-1]
                scored_candidates = []
                for sol, t, h, mt in candidate_with_time:
                    improvement = max(0, current_best - t)
                    scored_candidates.append((sol, t, h, mt, improvement))
                scored_candidates.sort(key=lambda x: (x[1], -x[4]))
                candidate_with_time = [(x[0], x[1], x[2], x[3]) for x in scored_candidates]
            elif candidate_with_time:  # 只有当有候选解时才排序
                candidate_with_time.sort(key=lambda x: x[1])

            # 更新变异效果记录
            if candidate_with_time:
                top_candidates = candidate_with_time[:int(len(candidate_with_time) * 0.2)]
                for sol, t, h, mt in top_candidates:
                    base_time = self.calculate_completion_time(self.current_population[0])
                    if t < base_time:
                        self.mutation_effectiveness[mt]['total'] += (base_time - t)
                        self.mutation_effectiveness[mt]['count'] += 1

            # 精英解保护
            if self.use_elite_protection and candidate_with_time:
                current_elites = candidate_with_time[:self.elite_size]
                self.elite_pool.extend(current_elites)
                # 去重并保持最优
                unique_elites = {}
                for sol, t, h, mt in self.elite_pool:
                    if h not in unique_elites or t < unique_elites[h][1]:
                        unique_elites[h] = (sol, t, h, mt)
                self.elite_pool = list(unique_elites.values())
                self.elite_pool.sort(key=lambda x: x[1])
                self.elite_pool = self.elite_pool[:self.elite_size]

            # 构建新种群
            keep_count = self.population_size // 2
            new_population = []

            # 加入精英解
            if self.use_elite_protection and self.elite_pool:
                new_population.extend([sol for sol, _, _, _ in self.elite_pool])

            # 选择非禁忌的优质解
            if candidate_with_time:
                for candidate, t, candidate_hash, mt in candidate_with_time:
                    if len(new_population) >= keep_count:
                        break
                    if candidate_hash not in self.tabu_list or t < self.best_time:
                        new_population.append(candidate)
                        self.tabu_list.append(candidate_hash)
                        if len(self.tabu_list) > self.tabu_size:
                            self.tabu_list.pop(0)

            # 补充随机解
            while len(new_population) < self.population_size:
                new_sol = self.initialize_solution()
                new_population.append(new_sol)

            self.current_population = new_population

            # 更新全局最优
            current_best_time = float('inf')
            current_best_solution = None
            for sol in self.current_population:
                try:
                    t = self.calculate_completion_time(sol)
                    if t < current_best_time:
                        current_best_time = t
                        current_best_solution = sol
                except Exception as e:
                    print(f"计算种群解时间出错: {e}")

            if current_best_time < self.best_time:
                self.best_time = current_best_time
                self.best_solution = current_best_solution

            self.iteration_best_times.append(self.best_time)
            self.history_best_times.append(self.best_time)

            if iter % 10 == 0:
                print(f"{self.name} 第 {iter} 代: 最佳完成时间 = {self.best_time:.2f}, 禁忌长度 = {self.tabu_size}")

        # 记录执行时间
        self.execution_time = time.time() - start_time

        return self.best_solution, self.best_time


def plot_convergence_comparison(algorithms: List[BaseSchedulingAlgorithm]):
    """绘制算法收敛曲线对比"""
    plt.figure(figsize=(12, 8))
    styles = [
        {'color': 'blue', 'linestyle': '-', 'marker': 'o', 'label': algorithms[0].name},
        {'color': 'green', 'linestyle': '--', 'marker': 's', 'label': algorithms[1].name},
        {'color': 'red', 'linestyle': '-.', 'marker': '^', 'label': algorithms[2].name},
        {'color': 'purple', 'linestyle': ':', 'marker': 'd', 'label': algorithms[3].name}
    ]

    for i, algorithm in enumerate(algorithms):
        if i < len(styles):
            style = styles[i]
            plt.plot(range(1, len(algorithm.iteration_best_times) + 1),
                     algorithm.iteration_best_times,
                     color=style['color'], linestyle=style['linestyle'],
                     marker=style['marker'], markersize=4, linewidth=2, label=style['label'])

    plt.xlabel('迭代次数')
    plt.ylabel('最大完成时间')
    plt.title('不同算法收敛曲线对比')
    plt.grid(True, linestyle='--', alpha=0.7)
    plt.legend()
    plt.tight_layout()
    plt.show()


def save_results_to_csv(results: List[Dict], instance_path: str):
    """将算法结果保存到CSV文件，使用时间戳命名文件夹"""
    # 创建结果文件夹（时间戳命名）
    timestamp = datetime.now().strftime("%Y%m%d_%H%M%S")
    results_dir = os.path.join("algorithm_results", timestamp)
    os.makedirs(results_dir, exist_ok=True)

    # 提取算例文件名作为标识
    instance_name = os.path.basename(instance_path)

    # 构建CSV文件路径
    csv_filename = f"results_{instance_name}.csv"
    csv_path = os.path.join(results_dir, csv_filename)

    # 定义CSV列名
    fieldnames = ['timestamp', 'algorithm', 'best_time', 'execution_time',
                  'num_workpieces', 'num_components', 'max_iter']

    # 写入CSV文件
    with open(csv_path, 'w', newline='', encoding='utf-8') as csvfile:
        writer = csv.DictWriter(csvfile, fieldnames=fieldnames)
        writer.writeheader()
        for result in results:
            writer.writerow(result)

    print(f"算法结果已保存至: {csv_path}")
    return csv_path


def select_instance():
    """让用户选择要使用的算例文件"""
    print("===== 算例选择 =====")
    # 搜索当前目录及子目录下的所有气体调度算例
    instance_files = GasSchedulingInstanceGenerator.list_instances()

    if not instance_files:
        print("未找到任何气体调度算例文件！")
        # 询问是否生成一个新的测试算例
        create_new = input("是否生成一个新的测试算例集？(y/n): ").strip().lower()
        if create_new == 'y':
            print("生成多规模测试算例...")
            GasSchedulingInstanceGenerator.generate_multiple_instances()
            instance_files = GasSchedulingInstanceGenerator.list_instances()
            if not instance_files:
                print("生成算例失败，请重试")
                exit(1)
        else:
            exit(1)

    # 显示找到的算例文件
    print("找到以下算例文件：")
    for i, file_path in enumerate(instance_files, 1):
        # 尝试读取算例基本信息
        try:
            with open(file_path, 'r') as f:
                data = json.load(f)
                wp = data['parameters'].get('num_workpieces', '未知')
                comp = data['parameters'].get('num_components', '未知')
                print(f"{i}. {file_path} (工件数: {wp}, 组分数: {comp})")
        except:
            print(f"{i}. {file_path} (格式可能不正确)")

    # 让用户选择
    while True:
        try:
            choice = int(input(f"请选择要使用的算例 (1-{len(instance_files)}): ")) - 1
            if 0 <= choice < len(instance_files):
                selected_file = instance_files[choice]
                print(f"已选择算例: {selected_file}")
                return selected_file, GasSchedulingInstanceGenerator.load_instance(selected_file)
            else:
                print(f"请输入1到{len(instance_files)}之间的数字")
        except ValueError:
            print("请输入有效的数字")


def select_algorithm():
    """让用户选择要运行的算法"""
    print("\n===== 算法选择 =====")
    algorithms = [
        {"code": "all", "name": "所有算法"},
        {"code": "ga", "name": "遗传算法(GA)"},
        {"code": "pso", "name": "粒子群优化(PSO)"},
        {"code": "sa", "name": "模拟退火(SA)"},
        {"code": "ts", "name": "改进禁忌搜索(TS)"}
    ]

    for i, algo in enumerate(algorithms, 1):
        print(f"{i}. {algo['name']}")

    while True:
        try:
            choice = int(input(f"请选择要运行的算法 (1-{len(algorithms)}): ")) - 1
            if 0 <= choice < len(algorithms):
                return algorithms[choice]['code']
            else:
                print(f"请输入1到{len(algorithms)}之间的数字")
        except ValueError:
            print("请输入有效的数字")


def main():
    """主函数"""
    parser = argparse.ArgumentParser(description='气体调度算法系统（支持算例选择、算法独立运行和结果保存）')
    parser.add_argument('--generate', action='store_true', help='生成默认算例集（设备随规模增加）')
    parser.add_argument('--instance', type=str, help='指定算例文件路径')
    parser.add_argument('--algorithm', type=str, choices=['all', 'ga', 'pso', 'sa', 'ts'],
                        help='选择算法')
    parser.add_argument('--max-iter', type=int, default=100, help='最大迭代次数')

    args = parser.parse_args()

    if args.generate:
        print("生成默认算例集（设备数量随工件规模增加）...")
        GasSchedulingInstanceGenerator.generate_multiple_instances()
        print("算例生成完成")
        return

    # 选择算例
    if args.instance:
        try:
            instance_path = args.instance
            instance = GasSchedulingInstanceGenerator.load_instance(instance_path)
        except Exception as e:
            print(f"加载指定算例失败: {e}")
            instance_path, instance = select_instance()
    else:
        instance_path, instance = select_instance()

    # 选择算法
    if args.algorithm is None:
        algorithm_code = select_algorithm()
    else:
        algorithm_code = args.algorithm

    # 初始化选中的算法
    algorithms = []
    if algorithm_code in ['all', 'ga']:
        ga = GeneticAlgorithm(
            instance=instance,
            population_size=50,
            generations=args.max_iter,
            crossover_rate=0.8,
            mutation_rate=0.1,
            name="遗传算法(GA)"
        )
        algorithms.append(ga)

    if algorithm_code in ['all', 'pso']:
        pso = ParticleSwarmOptimization(
            instance=instance,
            swarm_size=50,
            max_iter=args.max_iter,
            w=0.7,
            c1=1.5,
            c2=1.5,
            name="粒子群优化(PSO)"
        )
        algorithms.append(pso)

    if algorithm_code in ['all', 'sa']:
        sa = SimulatedAnnealing(
            instance=instance,
            init_temp=100.0,
            cool_rate=0.95,
            max_iter=args.max_iter,
            name="模拟退火(SA)"
        )
        algorithms.append(sa)

    if algorithm_code in ['all', 'ts']:
        ts = TabuSearch(
            instance=instance,
            population_size=100,
            tabu_size=20,
            neighborhood_size=10,
            max_iter=args.max_iter,
            use_elite_protection=True,
            dynamic_tabu_length=True,
            diverse_perturbation=True,
            history_heuristic=True,
            name="改进禁忌搜索(TS)"
        )
        algorithms.append(ts)

    # 运行选中的算法
    results = []
    for algo in algorithms:
        print(f"\n===== 开始运行 {algo.name} =====")
        best_solution, best_time = algo.optimize()
        print(f"{algo.name} 最佳完成时间: {best_time:.2f}")
        print(f"{algo.name} 执行时间: {algo.execution_time:.2f}秒")

        # 保存结果
        results.append(algo.get_results())

        # 绘制甘特图
        algo.plot_gantt_chart(title_suffix=f"(最佳完成时间: {best_time:.2f})")

    # 绘制收敛曲线对比（当运行多个算法时）
    if len(algorithms) > 1:
        plot_convergence_comparison(algorithms)

    # 保存结果到CSV文件
    save_results_to_csv(results, instance_path)


if __name__ == "__main__":
    main()